#include <iostream>
#include <vector>
#include <algorithm>
#include "TreeNode.h"
using namespace std;

pair<ListNode *, ListNode *> reverseList(ListNode *head)
{
    ListNode *past = head, *cur = head->next;
    past->next = nullptr;
    while (cur)
    {
        ListNode *next = cur->next;
        cur->next = past;
        past = cur;
        cur = next;
    }
    // 返回反转后新链表的头和尾
    return {past, head};
}

ListNode *reverseKGroup(ListNode *head, int k)
{
    ListNode *dummyHead = new ListNode(0);
    ListNode *pre = dummyHead, *cur = head;
    while (cur)
    {
        int k1 = k - 1;
        head = cur;
        while (cur && cur->next && k1)
        {
            cur = cur->next;
            k1--;
        }
        if (k1 > 0)
        {
            pre->next = head;
            break;
        }
        ListNode *next = cur->next;
        printf("next->val = %d\n", next->val);
        cur->next = nullptr;
        pair<ListNode *, ListNode *> res = reverseList(head);
        printf("head = %d\ntail = %d\n", res.first->val, res.second->val);
        pre->next = res.first;
        pre = res.second;
        cur = next;
    }
    head = dummyHead->next;
    delete dummyHead;
    return head;
}

int main()
{
    ListNode *L5 = new ListNode(5);
    ListNode *L4 = new ListNode(4, L5);
    ListNode *L3 = new ListNode(3, L4);
    ListNode *L2 = new ListNode(2, L3);
    ListNode *L1 = new ListNode(1, L2);
    ListNode *res = reverseKGroup(L1, 2);
    for (int i = 0; i < 5; i++)
    {
        printf("res->val = %d\n", res->val);
        res = res->next;
    }
    return 0;
}